
package com.colter.project.data.structure.graph;

import java.util.Stack;

//弗洛伊德算法  求任意两点间的最短距离
public class Floyd {
	public static void main(String[] args) {

		// 有向图
		int[][] weight = { 
				{ 0, 100, 20, 9999, 30 }, 
				{ 9999, 0, 5, 9999, 10 }, 
				{ 9999, 9999, 0, 30, 9999 },
				{ 9999, 5, 9999, 0, 9999 }, 
				{ 9999, 9999, 9999, 40, 0 }
				};

		// //无向图
//		 int[][] weight = {
//		 { 0, 3, 5, 99999, 99999 },
//		 { 3, 0, 99999, 2, 8 },
//		 { 5, 99999, 0, 6, 1 },
//		 { 99999, 2, 6, 0, 99999 },
//		 { 99999, 8, 1, 99999, 0 }
//		 };

		int[][] path = new int[weight.length][weight.length];

		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path[i].length; j++) {
				path[i][j] = -1;
			}
		}

		// 以 i为中心点 更新矩阵
		for (int k = 0; k < weight.length; k++) {
			for (int i = 0; i < weight.length; i++) {
				for (int j = 0; j < weight[i].length; j++) {
					if (weight[i][k] + weight[k][j] < weight[i][j]) {
						weight[i][j] = weight[i][k] + weight[k][j];
						path[i][j] = k;
					}
				}
			}
			
			System.out.println("更新矩阵:\n"+ k);
			for (int i = 0; i < weight.length; i++) {
				for (int j = 0; j < weight[i].length; j++) {
					System.out.print(weight[i][j]+ " ");
				}
				System.out.println();
			}
		}

		System.out.println("floy:\n");
		for (int i = 0; i < weight.length; i++) {
			for (int j = 0; j < weight[i].length; j++) {
				System.out.print(weight[i][j] + " ");
			}
			System.out.println();
		}

		System.out.println("path:\n");
		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path[i].length; j++) {
				System.out.print(path[i][j] + " ");
			}
			System.out.println();
		}

		// 直观 显示路径信息
		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path.length; j++) {
				int top = path[i][j];
				Stack<String> stack = new Stack<>();
				while (top != -1) {
					stack.push("->" + top);
					top = path[i][top];
				}
				StringBuffer sb = new StringBuffer();
				while (!stack.empty()) {
					sb.append(stack.pop());
				}
				if(i!=j){
					if(!"".equals(sb.toString())){
						System.out.println(i + "→" + j + "路径为:" + i + sb.toString() + "->" + j);
					}else{
						System.out.println(i + "→" + j + "路径为:直达");
					}
				}
			}
		}
	}

}
